This application is based on an application No. H11-069104 filed in Japan, the content of which is hereby incorporated by reference.
1. Field of the Invention
The present invention relates to exponentiation techniques and elliptic curve exponentiation techniques for use in areas such as cryptography.
2. Description of the Prior Art
Cryptographic communications allow specific terminals to securely communicate with each other in a network coupled to a plurality of terminals. One of cryptographic systems used for such cryptographic communications is the so-called public key cryptosystem. Examples of public key cryptosystems are the RSA (Rivest-Shamir-Adelman) and ElGamal systems. These public key cryptosystems perform exponentiation in encryption or decryption processing, in such a way as to exponentiate a message by an encryption key or exponentiate a ciphertext by a decryption key.
Another type of public key cryptosystems is a cryptosystem that uses elliptic curves. While other public key cryptosystems take a finite field as the domain of definition, the elliptic curve cryptosystem takes an elliptic curve as the domain of definition and performs elliptic curve exponentiation in encryption or decryption processing.
It is to be noted that exponentiation and elliptic curve exponentiation are used not only in the public key cryptosystems but in digital signature and message authentication schemes.
Knuth""s binary method (see D. E. Knuth xe2x80x9cSeminumerical Algorithmsxe2x80x9d The Art of Computer Programming, vol. 2 (1981)) is widely known as an algorithm for exponentiation and elliptic curve exponentiation. Also, the signed binary method (see F. Morain and J. Olivos xe2x80x9cSpeeding up the Computations on an Elliptic Curve using Addition-Subtraction Chainsxe2x80x9d Theoretical Informatics and Applications, vol. 24, no.6 (1990)) and the small window method (see the same document by Knuth) are known as improvements to the binary method. Further, Japanese Laid-Open Patent Application No. H07-049769 devises an improved signed binary method.
These conventional techniques are outlined below, taking modular exponentiation as an example.
(Binary Method)
The binary method, when given a binary representation ki(n greater than ixe2x89xa70) (where ki takes 0 or 1) of some exponent k, performs nxe2x88x921 modular squarings and a number of modular multiplications equivalent to a number of ones in ki, to obtain a modular exponentiation value.
Let the binary representation ki(4 greater than ixe2x89xa70))=1011. The binary method computes an exponentiation A1011 using arithmetic expressions given in FIG. 8.
First, 1 is assigned to x as an initial value. The most significant bit (MSB) of the exponent is interpreted as the first bit. If the first bit is 1, an operation of squaring x and setting x2 as x and an operation of multiplying x by A are performed in sequence. If the first bit is 0, only an operation of squaring x and setting x2 as x is performed. The same is repeated for each of the other bits of lesser significance. Consequently, x obtained after the least significant bit (LSB) has been processed is the exponentiation value A1011.
FIG. 9 is a flowchart showing the procedure of the binary method. In descending order from i=nxe2x88x921, the value of ki is checked (S71 and S76). If and only if ki=1 (S74), a modular multiplication is performed (S75). Meanwhile, a modular squaring is performed regardless of whether ki is 1 or 0 (S73). For a randomly chosen exponent k, this method takes n/2 modular multiplications on average. Also, since the exponent k is expressed in the ordinary binary representation, the method requires a storage of n bits for the exponent k.
FIG. 4 is a block diagram showing the general construction of a modular exponentiation device that carries out the above modular exponentiation.
In the figure, an exponent processing unit 101 processes an exponent k and also controls an exponentiation operation in an operating unit 106. Once the exponent k of n bits has been inputted in the modular exponentiation device through an input line 102, the exponent processing unit 101 accepts the exponent k as an initial value and processes the exponent k. The exponent processing unit 101 then outputs a control signal via an output line 103 to the operating unit 106, to control the exponentiation operation in the operating unit 106. In the meantime, a base A to be exponentiated by the exponent k is inputted in the modular exponentiation device via an input line 104 and received by the operating unit 106. The operating unit 106 performs the exponentiation operation, including modular squarings and modular multiplications, modulo a prime p for the base A, in accordance with the control signal. As a result, a modular exponentiation value Ak mod p is obtained and outputted from the operating unit 106 via an output line 105. Here, the prime p which acts as the modulus has been retained in the modular exponentiation device beforehand.
FIG. 10 is a block diagram showing the detailed construction of the exponent processing unit 101.
In the figure, a holding register 601 has an n-bit storage for holding the exponent k. The exponent k inputted in the modular exponentiation device is passed through an input line 602 to the holding register 601 as the initial value. A shifting unit 605 shifts the content of the holding register 601 by 1 bit to the left, as a result of which the MSB is shifted out and abandoned. This MSB is outputted from the holding register 601 via an output line 606 to the operating unit 106 as the control signal, according to which the processing content of the operating unit 106 is determined.
FIG. 11 is a block diagram showing the detailed construction of the operating unit 106. An intermediate value register 701 holds an intermediate value generated during the exponentiation operation. A constant 1 is inputted via an input line 702 into the intermediate value register 701 as an initial value. A squaring unit 703 performs a modular squaring on the intermediate value held in the intermediate value register 701 and outputs the result. A multiplying unit 704 performs a modular multiplication on the output of the squaring unit 703 by the base A and outputs the result. A selector 707 selects a new intermediate value to be stored in the intermediate value register 701, according to the control signal given from the exponent processing unit 101. If the control signal is 0, the selector 707 selects the output of the squaring unit 703, whereas if the control signal is 1, the selector 707 selects the output of the multiplying unit 704. After the above procedure is repeated for all n bits of the exponent k, Ak mod p is outputted through an output line 708.
(Signed Binary Method)
The signed binary method, when given a binary representation ki(n greater than ixe2x89xa70) (where ki takes 0 or 1) of some exponent k, transforms ki into a signed binary representation kxe2x80x2i(nxe2x89xa7ixe2x89xa70) (where kxe2x80x2i takes 0, 1, or xe2x88x921), and performs n modular squarings and a number of modular multiplications equivalent to a number of ones and minus ones in kxe2x80x2i, to obtain a modular exponentiation value. For instance, letting the binary representation ki(4 greater than ixe2x89xa70)=1111, then the signed binary representation is kxe2x80x2i(4xe2x89xa7ixe2x89xa70))=1000(xe2x88x921). Thus, when ki has a large number of consecutive ones, kxe2x80x2i will end up having a large number of zeros, thereby reducing the number of modular multiplications by the increase of zeros.
FIG. 12 is a flowchart showing the procedure of the signed binary method. In the figure, steps S101xcx9cS106 constitute the process of transforming a binary representation ki into a signed binary representation kxe2x80x2i, and steps S107xcx9cS114 constitute the process of applying the binary algorithm to the signed binary representation kxe2x80x2i. The latter process is analogous to the original binary method described above.
To transform the binary representation ki into the signed binary representation kxe2x80x2i, first the value of ki is checked in ascending order from i=0 (S101, S103, and S105). When ki=1 and k[i+1]=1, kxe2x80x2i is set to xe2x88x921 and 1 is added to k[i+1] with a carry being taken into account (S104). Otherwise, kxe2x80x2i is set to ki (S106). Due to the addition with carry, when the number of digits of ki is n, the number of digits of kxe2x80x2i is n +1. Next, the value of kxe2x80x2i is checked in descending order from i=n (S107, S110, and S113). If kxe2x80x2i=1, a modular multiplication is performed (S111), while if kxe2x80x2i=xe2x88x921, the inverse of a modular multiplication is performed (S112). Meanwhile, a modular squaring is performed regardless of whether kxe2x80x2i is 1, 0, or xe2x88x921, as with the original binary method (S109).
The signed binary method takes n/3 modular multiplications on average, for a randomly chosen exponent k. On the other hand, representing the exponent k by a signed binary number needs two bits per digit (in order to represent three values 0, 1, and xe2x88x921), so that the method requires a storage of 2(n+1) bits in total, for the exponent k.
FIG. 13 is a block diagram showing the construction of an exponent processing unit equipped in a modular exponentiation device that adopts the signed binary method. A holding register 901 has a storage of 2(n+1) bits to retain an exponent k in signed binary representation. A signed binary representation of the n-bit exponent k generated by a signed binary representation transforming unit 907 is inputted in the holding register 901 via an input line 902, as an initial value. The signed binary representation transforming unit 907 transforms the binary representation of n digits into the signed binary representation of n+1 digits, in accordance with the procedure shown in FIG. 12. A shifting unit 905 shifts the content of the holding register 901 by 2 bits to the left. This left shift of 2 bits is because each digit is represented by 2 bits in signed binary representation. Here, the higher order 2 bits are shifted out and as a result abandoned. The higher order 2 bits are then outputted from the holding register 901 via an output line 906 to an operating unit as a control signal, according to which the processing content of the operating unit is determined.
FIG. 14 is a block diagram showing the construction of the operating unit equipped in the modular exponentiation device that adopts the signed binary method. An intermediate value register 1001 holds an intermediate value generated during the exponentiation operation. A constant 1 is inputted in the intermediate value register 1001 through an input line 1002 as an initial value. A squaring unit 1003 performs a modular squaring on the intermediate value in the intermediate value register 1001 and outputs the result. A multiplying unit 1004 performs a modular multiplication on the output of the squaring unit 1003 by a base A or by the multiplicative inverse of A and outputs the result. A multiplicative inverse acquiring unit 1005 outputs the multiplicative inverse of A. A selector 1006 selects either the base A or the multiplicative inverse of A as a value to be inputted in the multiplying unit 1004, in accordance with the control signal given from the exponent processing unit. A selector 1007 selects a new intermediate value to be stored in the intermediate value register 1001, in accordance with the control signal given from the exponent processing unit. When the control signal is 00, the selector 1007 selects the output of the squaring unit 1003 as the new intermediate value. Otherwise, the selector 1007 selects the output of the multiplying unit 1004 as the new intermediate value. Once the above procedure has been done for all bits of the exponent k, Ak mod p is outputted through an output line 1008.
(Improved Signed Binary Method)
The improved signed binary method disclosed in Japanese Laid-Open Patent Application No. H07-049769, when given a binary representation ki(n greater than i240) (where ki takes 0 or 1) of an exponent k, performs operations such as modular multiplications while transforming the binary representation ki into a signed binary representation, to obtain a modular exponentiation value. Whereas the above signed binary method is batch processing that cannot launch the exponentiation operation until all bits of the exponent k are transformed, the improved signed binary method can conduct the exponentiation operation while the transformation is in progress.
FIG. 15 is a flowchart showing the procedure of the improved signed binary method. The value of ki is checked in units of 3 bits in descending order from i=nxe2x88x921 (S133), as a result of which 2 of the 3 bits are transformed into signed binary representation and operations such as modular multiplications are performed. This method takes 3n/8 modular multiplications on average for a randomly chosen exponent k. Also, since the signed binary transformation and the modular exponentiation operation are carried out in parallel, the method requires only a storage of n bits for the exponent k.
FIG. 16 is a block diagram showing the construction of an exponent processing unit equipped in a modular exponentiation device that employs the improved signed binary method. A holding register 1201 has a capacity of n+2 bits and holds an exponent k in signed binary representation. The n-bit exponent k is inputted in the holding register 1201 via an input line 1202 as an initial value. A judging unit 1203 judges a bit pattern of the higher order 3 bits in the holding register 1201. A shifting unit 1205 shifts the content of the holding register 1201 by 2 bits to the left. This left shift of 2 bits is because a control signal to control two operations in an operating unit is generated in one judgement process. Here, the higher order 2 bits are shifted out and as a result abandoned. The control signal showing the judgement result is outputted from the judging unit 1203 to the operating unit through an output line 1206, to determine the processing content of the operating unit.
FIG. 2 is a block diagram showing the construction of the operating unit equipped in the modular exponentiation device that employs the improved signed binary method. An intermediate value register 301 holds an intermediate value generated during the exponentiation operation. A constant 1 is inputted in the intermediate value register 301 via an input line 302 as an initial value. A squaring unit 303 performs a modular squaring on the intermediate value in the intermediate value register 301 and outputs the result. A multiplying unit 304 performs a modular multiplication on the output of the squaring unit 303 by a base A or by the multiplicative inverse of A and outputs the result. A multiplicative inverse acquiring unit 305 outputs the multiplicative inverse of A. A selector 306 selects either the base A or the multiplicative inverse of A as a value to be inputted in the multiplying unit 304, according to the control signal given from the exponent processing unit. A selector 307 selects either the output of the squaring unit 303 or the output of the multiplying unit 304 as a new intermediate value to be stored in the intermediate value register 301, according to the control signal given from the exponent processing unit. After the above procedure is repeated for every bit of the exponent k, Ak mod p is outputted through an output line 308.
FIG. 17 shows a table, referenced by the judging unit 1203 in the exponent processing unit, that associates bit patterns of the higher order 3 bits with patterns of first and second operations to be performed by the operating unit. A column 1301 shows the bit pattern of the higher order 3 bits, whereas a column 1303 shows the operation pattern to be applied by the operating unit. When xe2x80x9cmultiplication by Axe2x80x9d is indicated, the selector 306 in the operating unit selects the base A as the value to be inputted in the multiplying unit 304, and the selector 307 selects the output of the multiplying unit 304 as the new intermediate value. When xe2x80x9cmultiplication by Axe2x88x921xe2x80x9d is indicated, the selector 306 selects the multiplicative inverse of A as the input value of the multiplying unit 304, and the selector 307 selects the output of the multiplying unit 304 as the new intermediate value. When xe2x80x9cno multiplicationxe2x80x9d is indicated, on the other hand, the selector 307 selects the output of the squaring unit 303 as the new intermediate value. Likewise, a column 1304 in the table shows the operation pattern to be applied by the operating unit in a loop following the first operation in the column 1303. Thus, one judgement process by the judging unit 1203 in the exponent processing unit allows the contents of two operations by the operating unit to be determined.
However, the original binary method takes a squaring for every bit of an exponent and a multiplication by A for every zero bit. This means that 1.5 operations per bit are required on average. Thus, a large amount of computation is needed in the binary method.
The signed binary method can reduce the amount of computation of the original binary method. However, storing an exponent in signed binary representation costs a storage at least twice as large as that of the binary method.
Likewise, the small window method, though its explanation has been omitted, can further reduce the amount of computation of the binary method but requires a still larger storage for the exponent.
The improved signed binary method can reduce the average amount of computation to approximately that of the signed binary method, without the size of the exponent storage of the original binary method being increased. Nevertheless, the performance of the improved signed binary method is poor for a specific bit pattern, such as 0010, of an exponent. The original binary method takes only one modular multiplication for the bit pattern 0010, since the number of modular multiplications needed is equal to the number of one bits. In comparison, the improved signed binary method takes two modular multiplications for the same bit pattern, as can be seen from the table in FIG. 17. This indicates that the improved signed binary method in the worst case requires double the number of modular multiplications of the original binary method.
It should be noted that, though the above problems concern exponentiation, the same holds true for elliptic curve exponentiation. Therefore, solutions to these problems are important in not only exponentiation but elliptic curve exponentiation, for the efficient implementation of public key cryptosystems.
The first object of the invention is to provide an exponentiation device that can limit the number of multiplications in exponentiation to approximately that of the signed binary method on average and to that of the original binary method in the worst case, while maintaining the size of the exponent storage close to that of the original binary method.
The second object of the invention is to provide an exponent preprocessing unit improved to reduce the number of multiplications, in an exponentiation device that preprocesses an exponent and performs exponentiation with the preprocessed exponent.
The third object of the invention is to provide an exponentiation method for use in an exponentiation device, that can reduce the size of the exponent storage and the number of multiplications.
The fourth object of the invention is to provide a storage medium storing an exponentiation program for implementing the above exponentiation method.
The fifth object of the invention is to provide a modular exponentiation device, a modular exponentiation method, and a storage medium storing a modular exponentiation program that deliver the same advantages and effects as the above exponentiation device, exponentiation method, and storage medium storing the exponentiation program.
The sixth object of the invention is to provide an elliptic curve exponentiation device, an elliptic curve exponentiation method, and a storage medium storing an elliptic curve exponentiation program that deliver the same advantages and effects as the above exponentiation device, exponentiation method, and storage medium storing the exponentiation program.
The first and second objects can be fulfilled by an exponent preprocessing unit in an exponentiation device in which the exponent preprocessing unit preprocesses an n-bit exponent k and an operating unit exponentiates a base A by the preprocessed exponent k to compute Ak, the exponent preprocessing unit including: a bit string storing unit for storing a bit string including a sign bit and the exponent k; a reading unit for reading from the bit string storing unit a bit pattern composed of the sign bit and a bit sequence made up of a predetermined number of bits, the predetermined number being smaller than n; a bit pattern generating unit for generating a new bit pattern based on the bit pattern read by the reading unit; an operation pattern specifying unit for specifying an operation pattern to be applied to the base A, based on the read bit pattern; an instructing and changing unit for instructing the operating unit to perform an operation according to the operation pattern specified by the operation pattern specifying unit, and changing the read bit pattern to the new bit pattern and writing the new bit pattern back into the bit string storing unit in bit positions from which the bit pattern was read; a read position setting unit for having the reading unit read a next bit sequence starting from a different bit in the bit string in the bit string storing unit; and a repeat controlling unit for having the reading unit, the bit pattern generating unit, the operation pattern specifying unit, the instructing and changing unit, and the read position setting unit sequentially repeat respective procedures thereof n+1 times.
Here, the read position setting unit may upshift the bit string in the bit string storing unit excluding the sign bit, wherein the bit pattern read by the reading unit is composed of higher order 4 bits including the sign bit in the bit string storing unit.
Here, the bit pattern generating unit may have a table in which first bit patterns in a first column are associated with second bit patterns in a second column, wherein the bit pattern generating unit searches the first column for a first bit pattern that matches at least part of the bit pattern read by the reading unit, retrieves from the second column a second bit pattern which is associated with the first bit pattern, and sets the retrieved second bit pattern as the new bit pattern.
Here, the first bit patterns in the first column may be a 4-bit pattern 0011, a higher order 2-bit pattern 01, and a higher order 3-bit pattern 110, wherein the 4-bit pattern 0011 in the first column is associated with a 4-bit pattern 1001 in the second column, and the higher order 3-bit pattern 110 in the first column is associated with a higher order 3-bit pattern 010 in the second column, and wherein if neither the 4-bit pattern 0011 nor the higher order 3-bit pattern 110 in the first column matches at least part of the read bit pattern, the bit pattern generating unit sets the read bit pattern as the new bit pattern.
Here, the table may also include a third column that shows operation patterns which are associated with the first bit patterns in the first column, wherein if the first bit pattern that matches at least part of the read bit pattern is found, the operation pattern specifying unit specifies one of the operation patterns in the third column which is associated with the first bit pattern.
Here, the 4-bit pattern 0011 and the higher order 2-bit pattern 01 in the first column may be both associated with an operation pattern xe2x80x9cmultiplication by the base Axe2x80x9d in the third column, and the higher order 3-bit pattern 110 in the first column may be associated with an operation pattern xe2x80x9cmultiplication by a multiplicative inverse of the base Axe2x80x9d in the third column, wherein if the first bit pattern that matches at least part of the read bit pattern is not found, the operation pattern specifying unit specifies an operation pattern xe2x80x9cno multiplicationxe2x80x9d.
Here, the bit string storing unit may be a register of n+2 bits whose MSB (most significant bit) is the sign bit, and the read position setting unit may be a shifter for left shifting the bit string in the bit string storing unit excluding the MSB by 1 bit.
Here, the bit pattern generating unit may be provided with predetermined logical equations, to generate the new bit pattern by assigning to the logical equations values of the 4 bits which compose the read bit pattern.
Here, the logical equations in the bit pattern generating unit may be
D3={overscore (B2)}xc2x7B1xc2x7B0+B3xc2x7({overscore (B2)}+B1)
D2=B2
D1=B1xc2x7(B3+B2+{overscore (B0)})
D0=B0
where B3, B2, B1, and B0 respectively denote the values of the 4 bits which compose the read bit pattern in descending order of significance, and D3, D2, D1 and D0 respectively denote values of 4 bits which compose the new bit pattern in descending order of significance.
Here, the operation pattern specifying unit may be provided with predetermined logical equations, to specify the operation pattern by assigning to the logical equations values of the 4 bits which compose the read bit pattern.
Here, the logical equations in the operation pattern specifying unit may be
SA={overscore (B3)}xc2x7{overscore (B2)}xc2x7B1xc2x7B0+{overscore (B3)}xc2x7B2
SAxe2x88x921=B3xc2x7B2xc2x7{overscore (B1)}
where B3, B2, B1, and B0 respectively denote the values of the 4 bits which compose the read bit pattern in descending order of significance, SA denotes a signal showing whether to perform a multiplication by the base A, and SAxe2x88x921 denotes a signal showing whether to perform a multiplication by the multiplicative inverse of the base A.
With the above construction, the size of the storage for the n-bit exponent can be limited to n+2 bits. In addition, since the content of the operation is determined using the signed binary representation of the exponent, the number of multiplications needed in exponentiation can be reduced to about the average number of multiplications (one-third of n) of the signed binary method.
Further, since the change in the signed binary representation is registered to the bit string storing unit so as to be used for the next judgement, the number of multiplications needed will never exceed the number of multiplications of the original binary method.
Thus, the number of multiplications can be limited to approximately that of the signed binary method without the size of the exponent storage of the original binary method being significantly increased.
The first object can also be fulfilled by an exponentiation device for computing Ak using an n-bit positive integer k and an integer A, including: a storing unit having an exponent holding area of n+1 bits, a sign holding area for holding a sign, and an intermediate value holding area for holding an intermediate value generated during the computation of Ak; an initializing unit for initializing the storing unit by setting the integer k in lower order n bit positions in the exponent holding area, a value 0 in an MSB position in the exponent holding area, a positive sign + in the sign holding area, and a constant 1 in the intermediate value holding area; a squaring unit for squaring the intermediate value in the intermediate value holding area to obtain a square and replacing the intermediate value in the intermediate value holding area with the square to renew the intermediate value; a judgement object selecting unit for selecting the sign in the sign holding area and higher order 3 bits in the exponent holding area, as a judgement object; a judging unit for judging whether the judgement object has (a) a first pattern in which the sign in the sign holding area is the positive sign + and a bit pattern of the higher order 3 bits in the exponent holding area is 011, (b) a second pattern in which the sign in the sign holding area is the positive sign + and a higher order 1 bit in the exponent holding area is 1, (c) a third pattern in which the sign in the sign holding area is a negative sign xe2x88x92 and a bit pattern of higher order 2 bits in the exponent holding area is 10, or (d) none of the first pattern, the second pattern, and the third pattern; a multiplying unit for (1) if the judgement object has any of the first pattern and the second pattern, multiplying the intermediate value in the intermediate value holding area by the integer A to obtain a product and replacing the intermediate value in the intermediate value holding area with the product to renew the intermediate value, (2) if the judgement object has the third pattern, multiplying the intermediate value in the intermediate value holding area by a multiplicative inverse of the integer A to obtain a product and replacing the intermediate value in the intermediate value holding area with the product to renew the intermediate value, and (3) if the judgement object has none of the first pattern, the second pattern, and the third pattern, maintaining the intermediate value in the intermediate value holding area intact without performing any operation; a first changing unit for changing the sign in the sign holding area to the negative sign xe2x88x92 and the bit pattern of the higher order 3 bits in the exponent holding area to 001, if the judgement object has the first pattern; a second changing unit for changing the sign in the sign holding area to the positive sign +, if the judgement object has the third pattern; a shifting unit for left shifting a bit string of n+1 bits held in the exponent holding area by 1 bit and abandoning any bit that overflows, after procedures required depending on a judgement result by the judging unit are carried out; an outputting unit for outputting the intermediate value in the intermediate value holding area as Ak; and a controlling unit for firstly having the initializing unit initialize the storing unit, secondly having the squaring unit, the judgement object selecting unit, the judging unit, the multiplying unit, the first changing unit, the second changing unit, and the shifting unit sequentially repeat respective procedures thereof n+1 times, and lastly having the outputting unit output the intermediate value in the intermediate value holding area as Ak.
The modular exponentiation device of the fourth object and the elliptic curve exponentiation device of the fifth object have constructions same as or analogous to the exponentiation device. Accordingly, like the exponentiation device, the modular exponentiation device and the elliptic curve exponentiation device can reduce the number of multiplications needed, without having to significantly increase the size of the exponent storage.